package mo.tags.tree;

import mo.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class L95 {

    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        return generateTrees(1, n);
    }

    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> trees = new ArrayList<>();
        if (start > end) {
            trees.add(null);
            return trees;
        }

        for (int i = start; i <= end; i++) {
            List<TreeNode> allLeft = generateTrees(start, i-1);
            List<TreeNode> allRight = generateTrees(i+1, end);
            for (TreeNode left : allLeft) {
                for (TreeNode right : allRight) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    trees.add(root);
                }
            }
        }

        return trees;
    }

    public static void main(String[] args) {
        L95 test = new L95();
        List<TreeNode> treeNodes = test.generateTrees(3);
        System.out.println(treeNodes);
    }

}
